今天來介紹由內而外類型的動態規劃。基本上迴文字串、最佳二元搜尋樹類型的動態規劃就已經算是由內而外了！但有一些這類型的題目想起來還是覺得很精妙的。

Exercise 33: Leetcode 312 - Burst Balloons

題目連結

https://leetcode.com/problems/burst-balloons/

題目敘述

有 n 顆氣球，由左而右排開。你每次可以選一顆氣球戳，戳爆之後會獲得獎賞。獎賞取決於當前的氣球數值、還有當前左邊那顆氣球的數值、和右邊那顆氣球的數值的三數乘積。請找出最佳戳爆所有氣球的方案，使得總獎賞最大。你可以假設最邊邊的不存在的邊界氣球數值為 1。

解題思考

這題的關鍵在於考慮戳氣球的優先順序。相較於二元搜尋樹，我們選的那個「樹根」其實是對於其中一個連續的段落中，最後一個把它戳爆的氣球。也就是說，在 l, r 固定的情況下，我們考慮的是把這整段氣球 l+1, ..., r-1 戳爆時的最後一顆氣球是誰，此時你就會發現我們需要的子問題便是 (l, x), 和 (x, r) 把這兩段氣球戳爆。然後戳 x 得到的分數就是 nums[l] * nums[x] * nums[r]。

參考程式碼 (Python3)

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        dp = {}
        def compute(l, r):
            if dp.get((l, r)) != None:
                return dp[(l, r)]
            if l+1 == r:
                return 0
            ans = 0
            for k in range(l+1, r):
                ans = max(ans, compute(l, k) + compute(k, r) + nums[l] * nums[k] * nums[r])
            dp[(l, r)] = ans
            return ans
        nums = [1] + nums + [1]
        return compute(0, len(nums)-1)

Exercise 34: Leetcode 664 - Strange Printer

題目連結

https://leetcode.com/problems/strange-printer/submissions/

題目敘述

你想要刷出一個字串 S，但是每一次你可以選一段連續的位置，把它刷成同樣的形狀。請問你至少要刷幾次才能刷出 S？

解題思考

假設現在有底色 c，我們考慮的範圍是 [l, r] 這個範圍。那麼如果 c 跟 S[l] 同色，那麼顯然不需要重複刷 l 這個位置，因此答案跟考慮 [l+1, r] 這範圍、底色是 c 的最小刷數一樣。

如果 c 跟 S[l] 不同色，那麼顯然得花一單位時間把位置 l 刷成 S[l] 的顏色，這時候可以多刷一點東西。但可以注意到，如果一路刷過去，最後停下來的地方顏色與 S[l] 不同，那等於白刷。因此我們可以宣稱最佳解只會「在某個時刻」一路刷過去，然後刷到與 S[l] 相同的顏色停下來。假設這個位置是 S[k] 好了。假設最佳解中間某一步操作刷了 [l, k]，我們可以輕鬆把這一步搬到一開始來執行。因此，會變成 [l+1, k-1] 與 [k+1, r] 這兩個子問題、左半邊底色是 S[l]、右半邊底色是 c（因為根本沒動過）。

狀態總數 O(n^2c)，狀態轉移最壞情形 O(n)。

參考程式碼 (Python3)

class Solution:
    def strangePrinter(self, s: str) -> int:
        dp = {}
        def compute(l, r, c):
            if l > r:
                return 0
            if dp.get((l, r, c)) != None:
                return dp[(l, r, c)]
            if s[l] == c:
                dp[(l, r, c)] = compute(l+1, r, c)
                return dp[(l, r, c)]
            ans = sys.maxsize
            for k in range(l, r+1):
                if s[l] == s[k]:
                    ans = min(ans, 1 + compute(l+1, k-1, s[l]) + compute(k+1, r, c))
            dp[(l, r, c)] = ans
            return ans
        return compute(0, len(s)-1, None)